package com.zdp.leetcodeMiddle;


/*
* 题目描述：
* 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
注意:
每个数组中的元素不会超过 100
数组的大小不会超过 200
示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].
 

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/partition-equal-subset-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 分割等和子集_416 {

    /*
     * 解题思路： 将数组分割成两个子集（不按顺序），两个子集的和相等
     *  sum * 2 = nums.sum() -----> sum = nums.sum() /2
     *  可以转换为 0-1背包问题： 在数组中选取一部分数，（只能选取一次），使其和为 sum
     *  利用动态规划求解： dp[i][j] 表示在数组 [0-i]中选取一部分数，是否能达到j值
     * */
    public boolean canPartition(int[] nums) {
        int target = 0;
        int length = nums.length;
        int maxNum = Integer.MIN_VALUE;
        if(length < 2){
            return false;
        }
        for(int i=0; i < length ;i ++){
            target += nums[i];
            maxNum = Math.max(maxNum,nums[i]);
        }
        if( target % 2 !=0){
            return false;
        }
        target = target/2;
        if(maxNum > target){
            return false;
        }
        boolean[][] dp = new boolean[length][target+1];
        // 边界条件
        dp[0][nums[0]] = true;
        for(int i =0;i<length;i++){
            dp[i][0] = true;
        }
        // 为什么i 从1 开始？ ---> nums[0][nums[0] = true; 其余的值都为false
        for(int i =1; i < length ; i++){
            for(int j = 1; j <= target; j++){
                if( nums[i] > j){
                    // 不会选中 nums[i]值
                    dp[i][j] = dp[i-1][j];
                }else{
                    // 可以选中 或者不选中
                    // 如果不选中nums[i]的话 dp[i][j] = dp[i-1][j]
                    // 如果选中 nums[i]的话 dp[i][j] = dp[i-1][ j - nums[i]]
                    dp[i][j] = dp[i-1][j] || dp[i-1][j - nums[i]];
                }
            }
        }
        return dp[length-1][target];
    }

    /*
    * 优化空间
    * */
    public boolean canPartition1(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, maxNum = 0;
        for (int num : nums) {
            sum += num;
            maxNum = Math.max(maxNum, num);
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        if (maxNum > target) {
            return false;
        }
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;
        for (int i = 0; i < n; i++) {
            int num = nums[i];
            /*
            * 为什么从后往前遍历： 首先我们要知道 dp[j] |= dp[j - num]; 式子中的 dp[j]所代表的含义
            * dp[j] = dp[j] | dp[j-num]  等号前面的dp[j] 表示的是 dp[i][j]
            * 而等号后面的 dp[j] 表示的是 dp[i-1][j]
            *  其中，dp[j] 表示不拿 nums[i]的情况 ，dp[j-num]表示拿num[i]的情况
            * 如果 从 0开始遍历的话，那么你的 dp[j-num] 不能保证是没拿过num[i]的
            * （也就是说，j-num可能在之前就被处理过了,此时的dp[j-num] 不是表示 dp[i-1][j-num] 也是表示 dp[i][j-num]了）
            * */
            for (int j = target; j >= num; --j) {
                dp[j] |= dp[j - num];
            }
        }
        return dp[target];
    }
}
